Partition Labels
Leetcode #763 | Medium | Жадный алгоритм | O(26)
Идея
Жадный алгоритм. Запонимаем все последние индексы букв в int[26]. Заводим start и end, сдвигаем end, если i==endто обновляем старт а перед этим записываем в ответ end-start+1
Big-O
- Время
O(N) - Память
O(1)
Код
class Solution {
public List<Integer> partitionLabels(String s) {
int[] lastIdx = new int[26];
for (int i = 0; i < s.length(); i++) lastIdx[s.charAt(i) - 'a'] = i;
int start = 0, end = 0;
List<Integer> res = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, lastIdx[s.charAt(i) - 'a']);
if (i == end) { res.add(end - start + 1); start = i + 1; }
}
return res;
}
}